#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define Raghad ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pub push_back
#define pok pop_back
#define puf push_front
#define pof pop_front
#define fr first
#define se second
#define MOD 1000000007
#define nl "\n"
#define loop(j,n) for(int i=j;i<n;i++)
#define mkp make_pair
#define big begin()
#define en end()
#define all(v) v.begin(),v.end()
#define is(f) if(f)cout <<"YES\n";else cout << "NO\n";
vector < vector <pair <ll, ll> >> adj;
map<ll, bool>vis;
vector < pair <ll, ll> > edge,r;
ll dist[1050][1050];
priority_queue < pair < ll , ll > , vector<pair<ll, ll>>, greater<pair<ll, ll> > > pq;
void initialize(ll n,ll m) {
adj = vector < vector <pair <ll, ll> >>(n+1);
loop(1, n + 1)
for(int j=1;j<=n;j++)
dist[i][j] = 1e12;
ll x, y, w;
loop(0, m) {
cin >> x >> y >> w;
edge.pub({ x, y });
adj[x].pub({ y,w });
adj[y].pub({ x,w });
}
}
void dijkstra(ll s) {
ll node, minVal,newDist;
pq.push({ 0,s });
dist[s][s] = 0;
while (!pq.empty()) {
node = pq.top().se;
minVal = pq.top().fr;
pq.pop();
vis[node] = true;
if (dist[s][node] < minVal)continue;
for (auto child : adj[node]) {
if (!vis[child.fr]) {
newDist = dist[s][node] + child.second;
if (newDist < dist[s][child.fr]) {
dist[s][child.fr] = newDist;
pq.push({ dist[s][child.fr],child.fr });
}
}
}
}
}
int main() {
Raghad
ll t = 1;
//cin >> t;
while (t--) {
ll n, m, k,a,b,ans=1e12; cin >> n >> m >> k;
initialize(n, m);
loop(1,n+1)dijkstra(i),vis.clear();
loop(0, k) {
cin >> a >> b;
r.pub({ a,b });
}
for (auto i : edge) {
int x = i.fr, y = i.se, sum = 0;
for (auto j : r) {
int a = j.fr, b = j.se;
sum += min<ll>({ dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b] });
}
ans = min<ll>(ans, sum);
}
cout << ans;
}
}
274. H-Index | 260. Single Number III |
240. Search a 2D Matrix II | 238. Product of Array Except Self |
229. Majority Element II | 222. Count Complete Tree Nodes |
215. Kth Largest Element in an Array | 198. House Robber |
153. Find Minimum in Rotated Sorted Array | 150. Evaluate Reverse Polish Notation |
144. Binary Tree Preorder Traversal | 137. Single Number II |
130. Surrounded Regions | 129. Sum Root to Leaf Numbers |
120. Triangle | 102. Binary Tree Level Order Traversal |
96. Unique Binary Search Trees | 75. Sort Colors |
74. Search a 2D Matrix | 71. Simplify Path |
62. Unique Paths | 50. Pow(x, n) |
43. Multiply Strings | 34. Find First and Last Position of Element in Sorted Array |
33. Search in Rotated Sorted Array | 17. Letter Combinations of a Phone Number |
5. Longest Palindromic Substring | 3. Longest Substring Without Repeating Characters |
1312. Minimum Insertion Steps to Make a String Palindrome | 1092. Shortest Common Supersequence |